from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        lookup_table = set(nums)
        ans = 1
        for num in nums:
            # 这里会存在重复计算，为什么会产生以及如何解决，请参考 issue：
            # 比如 nums 为： 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 0 5 的时候，
            # 从遇到从第二个 0 及其后面的 0 的时候，不会执行 continue，而是会重复计算 ans
            # 因为在 lookup_table 中确实是没有 -1，
            # 怎么解决，请参考下面的 longestConsecutive2
            if num - 1 in lookup_table: continue
            curr_num, count = num, 1
            while curr_num + 1 in lookup_table:
                curr_num += 1
                count += 1
            ans = max(ans, count)
        return ans

    # 解决重复计算问题
    def longestConsecutive2(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        lookup_table = set(nums)
        ans, start, end = 1, None, None
        for num in nums:
            if start is not None and start <= num <= end:
                continue
            curr_num, count = num, 1
            while curr_num + 1 in lookup_table:
                curr_num += 1
                count += 1
            if count >= ans:
                ans = count
                start = num
                end = curr_num
        return ans

    def longestConsecutive1(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        nums.sort()
        ans = count = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]: continue
            if nums[i] == nums[i - 1] + 1:
                count += 1
                ans = max(ans, count)
            else:
                count = 1
        return ans

Solution().longestConsecutive([0, 1, 2, 3, 4, 0, 0, 0, 0, 0])